// 快排
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(time(nullptr));   // 种下一个随机数种子
        qsort(nums, 0, nums.size() - 1);
        return nums;
    }

    // 快排
    void qsort(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;

        // 数组分三块
        int key = getRandom(nums, l, r);
        int cur = l, left = l - 1, right = r + 1;
        while(cur < right)
        {
            if(nums[cur] < key)
                swap(nums[++left], nums[cur++]);
            else if(nums[cur] == key)
                cur++;
            else
                swap(nums[--right], nums[cur]);    
        }

        qsort(nums, l, left);
        qsort(nums, right ,r);
    }

    int getRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r % (right - left + 1) + left];
    }
};

//###############################################################
// 归并排序
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        MergeSort(nums, nums.size());

        return nums;
    }

    // 归并排序
    void MergeSort(vector<int>& nums, int n)
    {
        vector<int> tmp(n);
        _MergeSort(nums, 0, n - 1, tmp);
    }

    // 归并排序子程序
    void _MergeSort(vector<int>& nums, int left, int right, vector<int>& tmp)
    {
        if(left >= right)   return;

        int mid = (right - left) / 2 + left;    // 防溢出
        // 根据 mid 划分成两个序列：[left, mid] [mid + 1, right]
        _MergeSort(nums, left, mid, tmp);
        _MergeSort(nums, mid + 1, right, tmp);

        // 合并[left, mid] [mid + 1, right]
        int begin1 = left, end1 = mid;
        int begin2 = mid + 1, end2 = right;
        int index = begin1;
        while(begin1 <= end1 && begin2 <= end2)
        {
            if(nums[begin1] < nums[begin2])
                tmp[index++] = nums[begin1++];
            else
                tmp[index++] = nums[begin2++];
        }

        // 可能存在第一个序列中的数据没有全部放到 tmp 中
        while(begin1 <= end1)
            tmp[index++] = nums[begin1++];

        // 可能存在第二个序列中的数据没有全部放到 tmp 中
        while(begin2 <= end2)
            tmp[index++] = nums[begin2++];

        // 将 tmp 中的元素挪回 nums 数组
        for(int i = left; i <= right; ++i)
            nums[i] = tmp[i];
    }
};